import java.util.Arrays;

class Solution {
    public int pivotIndex2(int[] nums) {
        // 暴力枚举
        for (int i = 0; i < nums.length; i++) { // 确定中心下标
            // 计算出右侧的值
            int right_sum = 0;
            for (int j = i+1; j < nums.length; j++) {
                right_sum += nums[j];
            }
            // 计算出左侧的值
            int left_sum = 0;
            for (int k = i-1; k >= 0; k--) {
                left_sum += nums[k];
            }
            // 比较两个值
            if (left_sum == right_sum) {
                return i;
            }
        }
        return -1;
    }

    public int pivotIndex1(int[] nums) {
        // 前缀和优化
        // 创建两个辅助数组
        int n = nums.length;
        int[] right_nums = new int[n+2]; // 将原数组拷贝成新数组即可
        int[] left_nums = new int[n+1];
        for (int i = 1; i < n+1; i++) {
            left_nums[i] = left_nums[i-1] + nums[i-1];
        }
        for (int i = n; i > 0; i--) {
            right_nums[i] = right_nums[i+1] + nums[i-1];
        }
        for (int i = 0; i < nums.length; i++) { // 确定中心下标
            // 计算出右侧的值
            int right_sum = right_nums[i+2];
            // 计算出左侧的值
            int left_sum = left_nums[i];
            // 比较两个值
            if (left_sum == right_sum) {
                return i;
            }
        }
        return -1;
    }

    public int pivotIndex(int[] nums) {
        // 前缀和优化
        // 创建两个辅助数组
        int n = nums.length;
        int[] numsT = new int[n+1];
        // 指定要拷贝数组的范围
        System.arraycopy(nums, 0, numsT, 1, n);
        int[] right_nums = new int[n+2];
        int[] left_nums = new int[n+1];
        for (int i = 1; i < n+1; i++) {
            left_nums[i] = left_nums[i-1] + numsT[i];
        }
        for (int i = n; i > 0; i--) {
            right_nums[i] = right_nums[i+1] + numsT[i];
        }
        for (int i = 0; i < nums.length; i++) { // 确定中心下标
            // 计算出右侧的值
            int right_sum = right_nums[i+2];
            // 计算出左侧的值
            int left_sum = left_nums[i];
            // 比较两个值
            if (left_sum == right_sum) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        int[] array = new int[4];
        // array = Arrays.copyOfRange(nums, 1, 3);
        // 该方法可以指定要拷贝的数组的范围
        System.arraycopy(nums, 0,array,1,3);
    }
}